package Simple4;

public class Facebook_interview {
	
	/**
	 * You are given array of N positive integers, and an integer K. 
	 * Find two non-overlapping intervals, such that total number of elements in them is K, 
	 * and sum of elements is maximal.
		
		input:N=11, K=5,
		1 2 4 5 1 3 6 5 4 1 5

		output:
		24 = 4 + 5 + 6 + 5 + 4
	 * @param input
	 * @param k
	 * @return
	 */
	public static int findMax(int[] input,int k){
		//choose 2 intervals, sum1 is the first interval, sum2 is the second interval.
		if(input.length<k) return 0;
	    int sum1=0,sum2=0,total=0;
	    for(int i=1;i<k;++i){
	        int left = k-i;
	        for(int j=0;j<input.length-k+1;++j){
	            sum1=0;
	            for(int cur=j;cur<j+i;++cur){
	                sum1+=input[cur];
	            }
	            for(int m=j+i;m<input.length-left+1;++m){
	                sum2=0;
	                for(int cur=m;cur<m+left;cur++)                    
	                    sum2+=input[cur];
	                int temp= sum1+sum2;
	                if(temp>total) total = temp;
	            }
	        }              
	    }
	    return total;
	}
	
	public static int findMax2 (int[] input, int k) {
		int n = input.length;
		//sum1[j][i] means the max sum use i numbers choosing from first j numbers
		int[][] sum1 = new int[n+1][k+1];
		for (int i=1;i<=k;i++){
			int tempsum = 0;
			for (int j=1;j<=i;j++){
				tempsum = tempsum + input[j-1];
			}
			sum1[i][i] = tempsum;
			for (int j=i+1;j<=n;j++){
				tempsum = tempsum - input[j-i-1] + input[j-1];
				if (tempsum > sum1[j-1][i]){
					sum1[j][i] = tempsum;
				}
				else{
					sum1[j][i] = sum1[j-1][i];
				}
			}
		}
		int max = 0;
		for (int j=1;j<n;j++) {
			int sum2 = 0;
			for (int i=1;i<=k;i++) {
				if (j >= k-i && j+i-1 < n) {
					sum2 = sum2 + input[j+i-1];
					if (sum1[j][k-i]+sum2 > max) max = sum1[j][k-i] + sum2;
				}
			}
		}
		return max;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] test = {1,2,4,5,1,3,6,5,4,1,5};
		int k = 5;
		long start_time = System.nanoTime();
		System.out.println(findMax(test,k));
		long end_time = System.nanoTime();
		System.out.println(end_time-start_time);
	}

}
